package com.platform.modules.alg.alglib.hdu2896;

import java.util.LinkedList;
import java.util.Queue;

public class Hdu2896 {
    // ASCII 0-126,0-32无法显示
    public static int K = 126 - 32;
    boolean flag[] = new boolean[510];
    public String output = "";
    // 超根
    private node superRoot;
    // 树根
    private node root;

    // 初始化
    void init() {
        superRoot = new node();
        root = new node();
        root.fail = superRoot;
        for (int i = 0; i < K; i++)
            superRoot.ch[i] = root;
        superRoot.count = -1;
    }

    // Trie的插入
    void insert(String str, int id) {
        node t = root;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            int x = str.charAt(i) - '!'; // 第 33 个下标转化为0
            if (t.ch[x] == null)
                t.ch[x] = new node();
            t = t.ch[x];
        }
        t.count++;
        t.id = id;
    }

    void build_ac() {
        Queue<node> q = new LinkedList<>(); // 队列，BFS使用
        q.add(root);
        while (!q.isEmpty()) {
            node t;
            t = q.peek();
            q.poll();
            for (int i = 0; i < K; i++) {
                if (t.ch[i] != null) {
                    t.ch[i].fail = t.fail.ch[i];
                    q.add(t.ch[i]);
                } else
                    t.ch[i] = t.fail.ch[i];
            }
        }
    }

    boolean query(String str) {
        flag = new boolean[510];

        node t = root;
        boolean ok = false;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            int x = str.charAt(i) - '!'; // 第 33 个下标转化为0
            t = t.ch[x];
            for (node u = t; u.count != -1; u = u.fail) {
                if (u.count == 1) {
                    ok = true;
                    flag[u.id] = true;
                }
            }
        }
        return ok;
    }

    public String cal(String input) {
        int n, m;
        String[] line = input.split("\n");
        n = Integer.parseInt(line[0]);

        String str1;
        String str2;
        init();

        for (int i = 1; i <= n; i++) {
            str2 = line[i];
            insert(str2, i);
        }
        build_ac();
        m = Integer.parseInt(line[n + 1]);

        int cnt = 0;
        for (int i = 1; i <= m; i++) {
            str1 = line[n + 1 + i];

            if (query(str1)) {
                cnt++;
                output += "web " + i + ":";
                for (int j = 1; j <= n; j++)
                    if (flag[j])
                        output += " " + j;

                output += "\n";
            }
        }
        output += "total: " + cnt + "\n";
        return output;
    }
}

class node {
    node fail;
    node ch[] = new node[Hdu2896.K];
    int count;
    int id;

    node() {
        fail = null;
        for (int i = 0; i < ch.length; i++) {
            ch[i] = null;
        }
        count = 0;
        id = 0;
    }
}
